package com.tcs.test.tree.binary_tree;

/**
 * 二叉树
 */
public class BinaryTree implements Tree {

    private Node root;              // 表示根节点

    @Override
    public Node find(Integer key) {
        Node current = root;
        while (current != null) {
            if (current.data > key) {           // 节点值比key大,搜索左边
                current = current.leftChild;
            } else if (current.data < key) {    // 节点值比key小,搜索右边
                current = current.rightChild;
            } else {
                return current;
            }
        }
        return null;
    }

    @Override
    public boolean insert(Integer key) {
       Node newNode = new Node(key);
       if (null == root) {
           root = newNode;
           return true;
       } else {
           Node current = root;
           Node parentNode = null;
           while (null != current) {
               parentNode = current;
               if (current.data > key) {        // 节点值大于key,搜索左边
                   current = current.leftChild;
                   if (null == current) {
                       parentNode.leftChild = newNode;
                   }
               } else {        // 节点值小于key,搜索左边
                   current = current.rightChild;
                   if (null == current) {
                       parentNode.rightChild = newNode;
                   }
               }
           }
       }
       return false;
    }

    @Override
    public void infixOrder(Node current) {
        if (null != current) {
            infixOrder(current.leftChild);
            System.out.println("data : " + current.data);
            infixOrder(current.rightChild);
        }
    }

    @Override
    public Node root() {
        return root;
    }

    @Override
    public boolean delete(Integer key) {
        return false;
    }

    @Override
    public Node findMax() {
        Node current = root;
        Node maxNode = current;
        while (null != current) {
            maxNode = current;
            current = current.rightChild;
        }
        return maxNode;
    }

    @Override
    public Node findMin() {
        Node current = root;
        Node minNode = current;
        while (null != current) {
            minNode = current;
            current = current.leftChild;
        }
        return minNode;
    }
}
